package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import javax.print.DocFlavor;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class partition_ {
  StringBuilder sb = new StringBuilder();
  LinkedList<String> list = new LinkedList<>();
  List<List<String>> result = new LinkedList<>();

  @Test
  public void isPalindromeTest(){
    String s = "cabac";
    String s1 = "abccba";
    backTracking(s,0);
    System.out.println(result);
  }
  public void backTracking(String s,int index) {
    if (index >= s.length()){
      result.add(new LinkedList<>(list));
      return;
    }
    for (int i = index ; i < s.length() ; i ++){
      if (isPalindrome(s,index,i)){
        list.add(s.substring(index,i + 1));
      }else{
        continue;
      }
      backTracking(s,i + 1);
      list.removeLast();
    }
  }
  public boolean isPalindrome(String str,int start,int end){
    while(start < end){
      if (str.charAt(start++) != str.charAt(end--)){
        return false;
      }
    }
    return true;
  }
  public boolean isPalindromeList(List<String> list){
    for (String s : list) {
      if (!isPalindrome(s,0,s.length() - 1)){
        return false;
      }
    }
    return true;
  }
}
